Analysis of internet traffic reveals that for certain content types, which constitute a significant portion of the total traffic, a high degree of redundancy exists in the transmitted data. This manifests itself in the form of macro redundancies and micro redundancies. Macro redundancies are duplications of long byte strings, which occur when the same or similar data entities, (typically comprising hundreds of bytes or more) are repeatedly transmitted on a link between two end points. Micro redundancies occur due to the fine grain syntax underlying the byte sequences, which imposes a structure so that some smaller byte patterns (typically a few bytes in length) occur more frequently than others. Both of these types of redundancies can be exploited by data compression techniques to transmit the data more efficiently. The benefit is conservation of communication link resources (such as channel bandwidth and power) and an improvement in the user experience due to lower latency and faster response time.
Redundancies in a data stream can appear at many levels. At the highest level, an entire web page or document that was previously transmitted may be retransmitted on the data stream (e.g., due to a user repeatedly requesting the web page). At a lower level, an object within a web page (e.g., an image of an advertisement) may be frequently retransmitted, because it is common across multiple popular web pages. At the lowest level, a byte segment that was previously transmitted may reappear on the data stream. Each of these redundancies can be exploited by preventing the retransmission of the duplicate data, provided appropriate memory and processing techniques are employed at both ends of the connection.
Further, the range (e.g., the separation of the number of transmitted bytes from an occurrence of a byte segment to its redundant occurrence) over which redundancies occur in the data stream can span from a few bytes to several tens or hundreds of megabytes. This range may depend on several factors such as the type of content, speed of the link, usage pattern of the user, the number of users attached to the end point etc. Moreover, the redundancies can be micro redundancies, where the duplications are only a few bytes long or much longer macro redundancies.
Lossless data compression is a technique that compresses data streams for transmission over communications link by reducing data redundancies within the data streams, facilitating improved efficiency and utilization of link capacity. Lossless data compression algorithms exploit statistical redundancy to represent data more concisely, without losing information. A compressor is used to compress packets at one end of the link. At the other end of the link, a decompressor losslessly recovers the original packets.
There exists a class of data compression techniques known as long range data compression, which refers to compression techniques that compress data based on a relatively large data dictionary reflecting one or more data streams over a corresponding historical length of time. In conventional applications of such techniques, the length of time is proportional to the size of the dictionary—the larger the dictionary, the larger the ability to compress exploiting redundancy over longer data history.
Another class of data compression techniques exists, which are referred to as short-range data compression techniques. Rather than relying on a large dictionary (a long historical view of the data stream), short-range data compression techniques operate on small data sets, such as grammar-based algorithms, such as Yang-Kieffer (YK) universal data compression (see, e.g., U.S. Pat. Nos. 6,400,289 and 6,492,917). For example, grammar-based algorithms construct context-free grammar deriving from a single string, and also may apply statistical predictions referred to as arithmetic coding. Other examples of short-range compression techniques belong to the Lempel-Ziv family of compressors (LZ77 and LZ78, and derivatives thereof, such as gzip, compress, or V.44).
Conventional lossless data compression techniques have a stringent requirement that the packets cannot be reordered or lost during transport from the compressor to the decompressor. However, when traffic is transported as prioritized streams, this requirement can only be met on a per-stream basis, rather than the aggregate traffic as a whole. This is because a packet transported on a higher priority stream can overtake a packet transported on a lower priority stream. For example, in the case of a higher priority packet and a lower priority packet, where the higher priority packet is compressed later in time than the lower priority packet, but is provided transmission priority over the lower priority packet, the higher priority packet (while actually later in time at the compressor) will arrive at the decompressor earlier in time from the lower priority packet. Hence, the packets will arrive at the decompressor out of order, which would result in a failure of the decompression if it is applied to the aggregate traffic. Consequently, traditional compression techniques can be applied only on a per-stream basis and not on the aggregate traffic.
U.S. Patent Publication No. 2014/0223030 describes one method of applying multistream long range compression on multiple streams on an aggregated basis. U.S. Patent Publication No. 2014/0223030, however, requires a byte cache extension of the decompressor (i.e., the decompressor cache is larger than the compressor cache) to handle packets received out of order, which requires the use of additional memory.